# Python 2.6.4
# Project Euler, Problem 113
# Copyright 2010 Talha Zaman

def nonbouncy(digit):
    base, next = range(11), [0]*11
    down, both = 0, 9*(digit-1)+10
    for digits in range(digit-1):
        down += base[10] - 1
        for i in range(11):
            next[i] = sum([base[j] for j in range(i+1)])
        base, next = next, [0]*11
    return 2*base[10]+down-both-1

print nonbouncy(100)
